#include <iostream>
#include <algorithm>
#include <vector>

#define all(x) begin(x), end(x)

using namespace std;
const int N = 1e5 + 7, mod = 111121, g = 7;

int qpow(int a, int x) {
	int r = 1; a %= mod, x %= mod - 1;
	for (; x; x >>= 1, a = 1ll * a * a % mod)
		if (x & 1) r = 1ll * r * a % mod;
	return r;
} 

int lg[mod], pw[mod];
void init() {
	for (int i = pw[0] = 1; i < mod; ++i) {
		lg[pw[i] = pw[i - 1] * g % mod] = i;
	}
}

int spow(int x, int k) {
	if (x % mod == 0) return 0;
	return pw[1ll * k * lg[x % mod] % (mod - 1)];
}

vector<int> G[N];
int a[N], ans = 0;
struct Val {
	int x, y, c;
	bool operator < (const Val &v) const { return x != v.x ? x < v.x : y < v.y; }
	bool operator == (const Val &v) const { return x == v.x && y == v.y; }
} tmp[N];
vector<Val> f[N];

void dfs(int x, int p) {
	f[x].push_back({a[x], a[x], 1});
	ans = (ans + spow(a[x], a[x])) % mod;
	
	for (int y : G[x]) {
		if (y == p) continue;
		dfs(y, x);
		
		for (auto &v : f[y]) {
			v.x &= a[x], v.y |= a[x];
			for (auto u : f[x]) {
				ans = (ans + 1ll * spow(v.x & u.x, v.y | u.y) * v.c * u.c % mod) % mod;
			}
		} merge(all(f[x]), all(f[y]), tmp);
		
		int n = f[x].size() + f[y].size();
		f[x].clear();
		for (int i = 0; i < n; ++i) {
			if (tmp[i].x == 0)
				continue;
			else if (f[x].empty() || !(f[x].back() == tmp[i]))
				f[x].push_back(tmp[i]);
			else
				(f[x].back().c += tmp[i].c) %= mod; 
		}
	}
}

int main() {
	freopen("abstract.in","r",stdin);
	freopen("abstract.out","w",stdout);
	
	cin.tie(0)->sync_with_stdio(false);
	init();
	
	int n; cin >> n;
	for (int i = 1; i <= n; ++i) cin >> a[i];
	for (int x, y, i = 1; i < n; ++i) {
		cin >> x >> y;
		G[x].push_back(y), G[y].push_back(x);
	} dfs(1, 0);
	
	cout << ans << '\n';
}
